package dfs_and_bfs

type tGraphVisitor struct {
}

func newGraphVisitor() IGraphVisitor {
	return &tGraphVisitor{
	}
}

func (me *tGraphVisitor) createQueue(policy VisitPolicy) iNodeQueue {
	switch policy {
	case BFSPolicy:
		return newFIFOQueue()

	case DFSPolicy:
		return newLIFOQueue()

	default:
		panic("unsupported policy")
	}
}

func (me *tGraphVisitor) Visit(root INode, policy VisitPolicy) []INode {
	queue := me.createQueue(policy)
	queue.Push(root)

	visited := make(map[string]bool, 0)
	result := make([]INode, 0)
	for !queue.Empty() {
		_,node := queue.Poll()
		visited[node.ID()] = true
		result = append(result, node)

		children := node.Children()
		if children != nil {
			for _,it := range children {
				ok,_ := visited[it.ID()]
				if ok {
					continue
				}
				queue.Push(it)
			}
		}
	}

	return result
}

var GraphVisitor = newGraphVisitor()